//
//  Problem436.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/31.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 436. 寻找右区间
 给你一个区间数组 intervals ，其中 intervals[i] = [starti, endi] ，且每个 starti 都 不同 。
 区间 i 的 右侧区间 可以记作区间 j ，并满足 startj >= endi ，且 startj 最小化 。
 返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ，则下标 i 处的值设为 -1 。

 示例 1：
     输入：intervals = [[1,2]]
     输出：[-1]
     解释：集合中只有一个区间，所以输出-1。
 示例 2：
     输入：intervals = [[3,4],[2,3],[1,2]]
     输出：[-1, 0, 1]
     解释：对于 [3,4] ，没有满足条件的“右侧”区间。
     对于 [2,3] ，区间[3,4]具有最小的“右”起点;
     对于 [1,2] ，区间[2,3]具有最小的“右”起点。
 示例 3：
     输入：intervals = [[1,4],[2,3],[3,4]]
     输出：[-1, 2, -1]
     解释：对于区间 [1,4] 和 [3,4] ，没有满足条件的“右侧”区间。
     对于 [2,3] ，区间 [3,4] 有最小的“右”起点。
 提示：
     1 <= intervals.length <= 2 * 104
     intervals[i].length == 2
     -106 <= starti <= endi <= 106
     每个间隔的起点都 不相同
 */
@objcMembers class Problem436: NSObject {
    func solution() {
        print(findRightInterval([[1,2]]))
        print(findRightInterval([[3,4],[2,3],[1,2]]))
        print(findRightInterval([[1,4],[2,3],[3,4]]))
    }
    
    /*
     区间比较：首先想到的肯定是先排序，然后根据排序取值
     1：所以排序的规则：
     我们需求是：拿到一个区间后，取这个区间的第二个值，然后去和其他区间的第一个值来比较，所以按照第一个值来排序
     2: 遍历源数组，拿每一个区间interval，使用二分法，找到比interval[1]大的最小值
     3: 走到后，我们需要确定这个区间在原来数组中位置，那么我们需要事先用哈希存储一下
     */
    func findRightInterval(_ intervals: [[Int]]) -> [Int] {
        // 0: 哈希记录每个区间的原来位置
        var map:[[Int] : Int] = [:]
        for (i, interval) in intervals.enumerated() {
            map[interval] = i
        }

        // 1: 根据第一个值来排序
        let sortList = intervals.sorted { f, s in
            return f[0] < s[0]
        }
        
        // 结果集
        var result:[Int] = Array(repeating: -1, count: intervals.count)
        
        // 2: 二分法查找比它大的最小值
        var l = 0, r = 0, mid = 0
        for (i, interval) in intervals.enumerated() {
            l = 0
            r = sortList.count-1
            
            while l < r {
                mid = l + (r - l) >> 1
                if sortList[mid][0] >= interval[1] {
                    r = mid
                } else {
                    l = mid + 1
                }
            }
            
            if l == sortList.count-1, sortList[l][0] < interval[1] {    // 未找到
                result[i] = -1
            } else {            // 找到，去哈希中取位置
                result[i] = map[sortList[l]]!
            }
        }
        
        return result
    }
}
